﻿#define  _CRT_SECURE_NO_WARNINGS 1
////////牛牛尝试在蒙住眼睛的情况下拿到旁边的金币，假设的坐标是(x, y) ，金币的坐标是(x1, y1) ，金币一定在牛牛在周围，即 | x_1 - x | +| y_1 - y | = 1 \∣x
////////1
////////​
////////−x∣ + ∣y
////////1
////////​
////////−y∣ = 1  请你判断牛牛应该往哪个方向伸手。
////////输入描述：
////////第一行输入 x, y 表示牛牛的坐标。
////////第二行输入 x1, y1 表示金币的坐标。保证 | x_1 - x | +| y_1 - y | = 1 \∣x
////////1
////////​
////////−x∣ + ∣y
////////1
////////​
////////−y∣ = 1
////////坐标是整数。
////////输出描述：
////////输出牛牛应该往哪个方向伸手。
////////例
////////(x, y) = (0, 0) (x1, y1) = (0, 1) ，则牛牛向上伸手，输出 'u' 。
////////(x, y) = (0, 0) (x1, y1) = (0, -1) ，则牛牛向下伸手，输出 'd'。
////////(x, y) = (0, 0) (x1, y1) = (1, 0) ，则牛牛向右伸手，输出 'r'。
////////(x, y) = (0, 0) (x1, y1) = (-1, 0) ，则牛牛向左伸手，输出 'l'。
//////#include <stdio.h>
////////int main()
////////{
////////    int a, b;
////////    int c, d;
////////    scanf("%d %d", &a, &b);
////////    scanf("%d %d", &c, &d);
////////    if (d > b)
////////    {
////////        printf("u");
////////    }
////////    if (d < b)
////////    {
////////        printf("d");
////////    }
////////    if (c > a)
////////    {
////////        printf("r");
////////    }
////////    if (c < a)
////////    {
////////        printf("l");
////////    }
////////
////////    return 0;
////////}
////////第一行输入 y ，m ，d ，即牛牛计划开始学习的时间。
////////第二行输入 y1，m1，d1，即询问的时间。
////////输出描述：
////////请你判断牛牛是否开始学习。如果是则输出 yes ，否则输出 no
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b, c;
////////    int d, e, f;
////////    scanf("%d %d %d", &a, &b, &c);
////////    scanf("%d %d %d", &d, &e, &f);
////////    if (d > a)
////////    {
////////        printf("yes");
////////        return 0;
////////    }
////////    else if (d < a)
////////    {
////////        printf("no");
////////        return 0;
////////    }
////////    if (d == a && b > e)
////////    {
////////        printf("no");
////////        return 0;
////////    }
////////    if (d == a && b < e)
////////    {
////////        printf("yes");
////////        return 0;
////////    }
////////    if (d == a && b == e && c > f)
////////    {
////////        printf("no");
////////        return 0;
////////    }
////////    if (d == a && b == e && c <= f)
////////    {
////////        printf("yes");
////////        return 0;
////////    }
////////    return 0;
////////}
//////// 针对每组输入，输出一行，输出一元二次方程ax2 + bx +c = 0的根的情况。
//////
////////如果a = 0，输出“Not quadratic equation”；
////////
////////如果a ≠  0，分三种情况：
////////
////////△ = 0，则两个实根相等，输出形式为：x1 = x2 = ...。
////////
////////△ > 0，则两个实根不等，输出形式为：x1 = ...; x2 = ...，其中x1 <= x2。
////////
////////△ < 0，则有两个虚根，则输出：x1 = 实部 - 虚部i; x2 = 实部 + 虚部i，即x1的虚部系数小于等于x2的虚部系数，实部为0时不可省略。实部 = -b / (2 * a), 虚部 = sqrt(-△) / (2 * a)
////////
////////	所有实数部分要求精确到小数点后2位，数字、符号之间没有空格。
////////#include <stdio.h>
////////#include<math.h>
////////int main()
////////{
////////    double a, b, c;
////////    while (scanf("%lf %lf %lf", &a, &b, &c) == 3)
////////    {
////////        if (a == 0)
////////        {
////////            printf("Not quadratic equation");
////////        }
////////        else
////////        {
////////            float tmp = b * b - 4 * a * c;
////////            if (tmp == 0)
////////            {
////////                if (((-b) / (2 * a)) == -0.0)
////////                {
////////                    printf("x1=x2=%.2lf", -(-b / (2 * a)));
////////                }
////////                else
////////                {
////////                    printf("x1=x2=%.2lf", (-b) / (2 * a));
////////                }
////////
////////            }
////////            else if (tmp > 0)
////////            {
////////                printf("x1=%.2lf;x2=%.2lf", (-b - sqrt(tmp)) / (2 * a), (-b + sqrt(tmp)) / (2 * a));
////////            }
////////            else
////////            {
////////                printf("x1=%.2lf-%.2lfi;x2=%.2lf+%.2lfi", -b / (2 * a), (sqrt(-tmp)) / (2 * a), -b / (2 * a), (sqrt(-tmp)) / (2 * a));
////////            }
////////        }
////////
////////    }
////////    return 0;
////////}
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b, c;
////////    scanf("%d %d %d", &a, &b, &c);
////////    int sum = (a + b + c) / 3;
////////    if (sum >= 60)
////////    {
////////        printf("NO");;
////////    }
////////    else
////////    {
////////        printf("YES");;
////////    }
////////    return 0;
////////}
//////
////////int main()
////////{
////////	char arr[10] = {0 };
////////	arr[0] = '1';
////////	arr[1] = '2';
////////	arr[2] = '3';
////////	arr[3] = '\0';
////////	int i = 0;
////////	printf("%s", arr);
////////
////////
////////}
//////
///////*识别码的计算方法如下：
//////首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0 - 670 - 82162 - 4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，…，9，再求和，即0×1 + 6×2 + …… + 2×9 = 158，然后取158 mod 11的结果4作为识别码。
//////////你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码*/。
//////////
////////#include <stdio.h>
////////int main()
////////{
////////    int ch = 0;
////////    int sum = 0;
////////    int count = 1;
////////    int flag = 1;
////////    char arr[100] = { 0 };
////////    int i = 0;
////////    while ((ch = getchar()) != EOF)
////////    {
////////
////////        if (i <= 11)
////////        {
////////            arr[i] = ch;
////////            i++;
////////        }
////////        if (ch >= 48 && ch <= 57 && count <= 9)
////////        {
////////            ch = ch - '0';
////////            sum += ch * count;
////////            count++;
////////        }
////////        if (ch >= 48 && ch <= 57 && count == 10 || ch == 'X')
////////        {
////////            if (ch == 'X')
////////            {
////////                flag = 10;
////////            }
////////            else
////////            {
////////                flag = ch - '0';
////////            }
////////
////////        }
////////
////////    }
////////    if (sum % 11 == flag)
////////    {
////////        printf("Right");
////////    }
////////    else
////////    {
////////        if ((sum % 11) == 10)
////////        {
////////            arr[12] = 'X';
////////            arr[13] = '\0';
////////        }
////////        else
////////        {
////////            arr[12] = sum % 11 + '0';
////////            arr[13] = '\0';
////////        }
////////
////////        printf("%s", arr);
////////    }
////////
////////    return 0;
//////////}
////////输出为一行。
////////
////////如果操作数和运算符号均合法，则输出一个表达式，操作数1运算符操作数2 = 运算结果，各数小数点后均保留4位，数和符号之间没有空格。
////////
////////如果输入的运算符号不包括在（ + 、 - 、 * 、 / ）范围内，输出“Invalid operation!”。当运算符为除法运算，即“ / ”时。
////////
////////如果操作数2等于0.0，则输出“Wrong!Division by zero!”。
////////示例1
////////#include <stdio.h>
////////int main()
////////{
////////    double n, m;
////////    char ch = 0;
////////    scanf("%lf %c %lf", &n, &ch, &m);
////////    switch (ch)
////////    {
////////    case '+':
////////    {
////////        printf("%.4lf+%.4lf=%.4lf", n, m, n + m);
////////        break;
////////    }
////////    case '-':
////////    {
////////        printf("%.4lf-%.4lf=%.4lf", n, m, n - m);
////////        break;
////////    }
////////    case '*':
////////    {
////////        printf("%.4lf*%.4lf=%.4lf", n, m, n * m);
////////        break;
////////    }
////////    case '/':
////////    {
////////        if (m == 0.0)
////////        {
////////            printf("Wrong!Division by zero!");
////////            break;
////////        }
////////        else
////////        {
////////            printf("%.4f/%.4f=%.4f", n, m, n / m);
////////            break;
////////        }
////////    }
////////    default:
////////        printf("Invalid operation!");
////////        break;
////////    }
////////
////////    return 0;
////////}
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b;
////////    scanf("%d %d", &a, &b);
//////////    printf("%d", a / b);
//////////    return 0;
////////////}
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b;
////////    scanf("%d %d", &a, &b);
////////    printf("%d", a % b);
////////    return 0;
////////}
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b;
////////    scanf("%d", &a);
////////    printf("%d", a % 10);
////////    return 0;
////////}
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b;
////////    scanf("%d", &a);
////////    a /= 10;
////////    printf("%d", a % 10);
////////    return 0;
////////}
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b;
////////    scanf("%d %d", &a, &b);
////////    if ((a + b) % 7 == 0)
////////    {
////////        printf("7");
////////    }
////////    else
////////    {
////////        printf("%d", (a + b) % 7);
////////    }
////////    return 0;
////////}
////////#include <stdio.h>
////////int main()
////////{
////////    long long a = 0;
////////    scanf("%d", &a);
////////    printf("%lld", a * 31560000);
////////    return 0;
////////}
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b;
////////    scanf("%d", &a);
////////    printf("%d", a * 100);
////////    return 0;
////////}
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b, c, d;
////////    scanf("%d %d %d %d", &a, &b, &c, &d);
////////    printf("%d", (a + b - c) * d);
////////    return 0;
////////}
////////#include <stdio.h>
////////#include<math.h>
////////int main()
////////{
////////    int a, b, c;
////////    scanf("%d %d %d", &a, &b, &c);
////////    float d = a + b + c;
////////    float p = d / 2;
////////    float f = sqrt(p * (p - a) * (p - b) * (p - c));
////////
////////    printf("circumference=%.2f area=%.2f", d, f);
////////    return 0;
////////}
////////#include <stdio.h>
////////int main()
////////{
////////    double a = 0;
////////    scanf("%lf", &a);
////////    double e = 5 * (a - 32) / 9;
////////    printf("%.3lf", e);
//////////    return 0;
//////////}
////////#include <stdio.h>
////////#define pi 3.14
////////int main()
////////{
////////    int r = 0;
////////    scanf("%d", &r);
////////    printf("%f", pi * r * r);
////////    return 0;
//////////}
////////
////////#include <stdio.h>
////////int main()
////////{
////////    float a, b;
////////    scanf("%f %f", &a, &b);
////////    double e = (a * b) / (a + b);
////////    printf("%lf", e);
////////
////////    return 0;
////////}
///////////*牛牛刚接触等差数列， 他知道等差数列是每项与前一项的差值都相等的数列，已知第一项 a 和第二项 b 的值，他想知道第三项是多*/少
//////////牛牛刚接触等差数列， 他知道等差数列是每项与前一项的差值都相等的数列，已知第一项 a 和第二项 b 的值，他想知道第三项是多少
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b;
////////    scanf("%d %d", &a, &b);
////////    int c = 0;
////////    printf("%d", b + (b - a));
////////    return 0;
////////}
////////#include <stdio.h>
////////#define pi 3.14
////////int main()
////////{
////////    float a;
////////    scanf("%f", &a);
////////    float e = (4 * pi * a * a * a) / 3.0;
////////    printf("%f", e);
////////
////////    return 0;
////////}
////////输入现在的时刻以及要睡的时长k（单位：minute），中间用空格分开。
////////
////////输入格式：hour : minute k(如hour或minute的值为1，输入为1，而不是01)
////////
////////(0 ≤ hour ≤ 23，0 ≤ minute ≤ 59，1 ≤ k ≤ 109)
////////#include <stdio.h>
////////int main()
////////{
////////    int a, b, c;
////////    scanf("%d:%d %d", &a, &b, &c);
////////    a = ((a + c / 60) + ((b + c % 60) / 60)) % 24;
////////    b = (b + c % 60) % 60;
////////    if (a < 10)
////////    {
////////
////////        if (b < 10)
////////        {
////////            printf("0%d:0%d", a, b);
////////        }
////////        else
////////        {
////////            printf("0%d:%d", a, b);
////////        }
////////    }
////////    else
////////    {
////////        if (b < 10)
////////        {
////////            printf("%d:0%d", a, b);
////////        }
////////        else
////////        {
////////            printf("%d:%d", a, b);
////////        }
////////    }
////////
////////    return 0;
////////}
//#include <stdio.h>
//int main()
//{
//    int n, m;
//    scanf("%d %d", &n, &m);
//    int max = (n > m ? n : m);
//    int min = (n < m ? n : m);
//    int i = 0;
//    int e = 0;
//    int t = 0;
//    for (i = min; i >= 0; i--)
//    {
//        if (max % i == 0 && min % i == 0)
//        {
//            e = i;
//            break;
//        }
//    }
//    for (i = max; i >= 0; i++)
//    {
//        if (i % max == 0 && i % min == 0)
//        {
//            t = i;
//            break;
//        }
//    }
//    printf("%d", e + t);
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//    long long n, m;
//    scanf("%lld %lld", &n, &m);
//    long long max = (n > m ? n : m);
//    long long min = (n < m ? n : m);
//    long long i = 0;
//    long long e = 0;
//    long long t = 0;
//    long long tmp1 = m;
//    long long tmp2 = n;
//    long long k = m % n;
//    while (k = m % n)
//    {
//        m = n;
//        n = k;
//    }
//    e = n;
//    t = (tmp1 * tmp2) / e;
//    printf("%lld", e + t);
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//    float a, b, c, d, e;
//    scanf("%f %f %f %f", &a, &b, &c, &d);
//    printf("%.1f", a * 0.2 + b * 0.1 + c * 0.2 + d * 0.5);
//    return 0;
//}
//#include <stdio.h>
//int main()
//{
//    int a, b, c, d, e;
//    scanf("%d %d %d %d", &a, &b, &c, &d);
//    printf("%d", (a - c) * (a - c) + (b - d) * (b - d));
//    return 0;
//}
//#include <stdio.h>
//#include<math.h>
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    if (n / 2 == 0)
//    {
//        printf("0");
//        return 0;
//    }
//    int tmp = n;
//    int sum = 0;
//    int count = 0;
//    while (tmp)
//    {
//        int a = tmp % 10;
//        if (a % 2 == 0)
//        {
//            sum += 0;
//        }
//        else
//        {
//            sum += (int)pow(10, count);
//        }
//
//        count++;
//        tmp /= 10;
//    }
//    printf("%d", sum);
//    return 0;
//}






